package org.algorithm.biubiu.wheel_1.数组.三月.第四周;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/24 8:38 PM
 * @description: 周五
 *
 *
 * url: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 */
public class 青蛙跳台阶 {

    // public int numWays(int n) {
    //     if(n==0) return 1;
    //     if(n<3) return n;

    // return numWays(n-1)+numWays(n-2) ;
    // }

    public int numWays(int n) {
        if(n==0) return 1;
        if(n<3) return n;

        int[] res = new int[3];
        res[0] = 1;
        res[1] = 2;
        for(int i=2;i<n;i++){
            res[i%3] = (res[(i-1)%3]+res[(i-2)%3])%1000000007;
        }
        return res[(n-1)%3];
    }
}
